//
// itertool - a polynormial and type-safe iterator framework in C++.
//
// Copyright (c) 2021-2025 Feng Cong
//
// Distributed under the MIT Software License
// See accompanying file LICENSE.txt or copy at
// https://opensource.org/licenses/MIT

#pragma once

#include <algorithm>
#include <cassert>
#include <memory>
#include <tuple>
#include <type_traits>
#include <vector>

#define ITERTOOL_VERSION_MAJOR 0
#define ITERTOOL_VERSION_MINOR 0
#define ITERTOOL_VERSION_PATCH 1
#define ITERTOOL_VERSION_STR "0.0.1"

#define ITERTOOL_VERSION                                           \
  (ITERTOOL_VERSION_MAJOR * 10000 + ITERTOOL_VERSION_MINOR * 100 + \
   ITERTOOL_VERSION_PATCH)

#ifdef __cpp_fold_expressions

#define ITERTOOL_DETAIL_FoldExpr_AllOf(pack) ((pack) && ...)
#define ITERTOOL_DETAIL_FoldExpr_AnyOf(pack) ((pack) || ...)
#define ITERTOOL_DETAIL_FoldExpr_ForEach(pack) ((void)(pack), ...)

#else

#define ITERTOOL_DETAIL_FoldExpr_AllOf(pack) \
  ::itertool::detail::fold_expr::AllOf({static_cast<bool>(pack)...})
#define ITERTOOL_DETAIL_FoldExpr_AnyOf(pack) \
  ::itertool::detail::fold_expr::AnyOf({static_cast<bool>(pack)...})
#define ITERTOOL_DETAIL_FoldExpr_ForEach(pack) \
  ::itertool::detail::fold_expr::ForEach({((pack), false)...})

#endif

namespace itertool {

template <typename T>
class Iterable {
 public:
  using ItemType = T;

  virtual bool HasNext() = 0;

  virtual ItemType GetNow() = 0;

  virtual void Advance() = 0;

  virtual bool IsFinite() { return false; }

  virtual bool IsResetable() { return false; }

  virtual void Reset() {}

  virtual size_t LengthHint() { return 0; }

  virtual ~Iterable() {}
};

template <typename T>
class InfiniteIterableBase : public Iterable<T> {
 public:
  using ItemType = T;

  bool HasNext() override { return true; }
  bool IsFinite() override { return false; }
  size_t LengthHint() override { return 0; }
};

template <typename T>
class Iterator {
 public:
  using ItemType = T;

  explicit Iterator(std::shared_ptr<Iterable<T>> iterable)
      : iterable_(iterable) {}

  Iterator() = default;
  Iterator(const Iterator&) = default;
  Iterator& operator=(const Iterator&) = default;

  bool IsEmpty() const { return !iterable_; }

  bool IsFinite() const {
    assert(iterable_);
    return iterable_->IsFinite();
  }

  bool IsResetable() const {
    assert(iterable_);
    return iterable_->IsResetable();
  }

  bool HasNext() const {
    assert(iterable_);
    return iterable_->HasNext();
  }

  ItemType GetNow() const {
    assert(HasNext());
    return iterable_->GetNow();
  }

  ItemType MaybeGetNow(ItemType value) const {
    return HasNext() ? GetNow() : value;
  }

  void Advance() const {
    assert(HasNext());
    return iterable_->Advance();
  }

  void MaybeAdvance() const {
    if (HasNext()) Advance();
  }

  void Reset() const {
    assert(iterable_);
    iterable_->Reset();
  }

  size_t LengthHint() const {
    assert(iterable_);
    return iterable_->LengthHint();
  }

  void Clear() { iterable_.reset(); }

  class iterator {
   public:
    using reference = ItemType;
    using iterator_category = std::forward_iterator_tag;
    using value_type = void;
    using pointer = void;
    using difference_type = ptrdiff_t;

    explicit iterator(Iterator<T> it) : it_(it) {}

    iterator() = default;
    iterator(const iterator&) = default;
    iterator& operator=(const iterator&) = default;

    bool operator!=(const iterator&) const { return it_.HasNext(); }
    bool operator==(const iterator&) const { return !it_.HasNext(); }

    reference operator*() const { return it_.GetNow(); }

    iterator& operator++() {
      it_.Advance();
      return *this;
    }

   private:
    Iterator<T> it_;
  };

  iterator begin() const { return iterator(*this); }
  iterator end() const { return iterator(); }

 private:
  std::shared_ptr<Iterable<T>> iterable_;
};

template <typename IterableCls, typename... Args,
          typename ItemType = typename IterableCls::ItemType>
Iterator<ItemType> MakeIterator(Args&&... args) {
  static_assert(std::is_base_of<Iterable<ItemType>, IterableCls>::value,
                "IterableCls must be a subclass of Iterable<T>");
  auto iterable_ptr =
      std::make_shared<IterableCls>(std::forward<Args>(args)...);
  return Iterator<ItemType>(std::move(iterable_ptr));
}

template <typename IterableCls, typename Enable = void>
struct IterableTraits {};

template <typename T>
struct IterableTraits<Iterator<T>> {
  using ItemType = T;
  using IterableCls = Iterator<T>;
  static bool HasNext(IterableCls it) { return it.HasNext(); }
  static ItemType GetNow(IterableCls it) { return it.GetNow(); }
  static void Advance(IterableCls it) { it.Advance(); }
  static bool IsFinite(IterableCls it) { return it.IsFinite(); }
  static bool IsResetable(IterableCls it) { return it.IsResetable(); }
  static void Reset(IterableCls it) { it.Reset(); }
  static size_t LengthHint(IterableCls it) { return it.LengthHint(); }
};

template <typename T>
Iterator<T>& Iter(Iterator<T>& it) {
  return it;
}

template <typename T>
Iterator<T>&& Iter(Iterator<T>&& it) {
  return std::move(it);
}

template <typename T>
using DeclareIterType =
    typename std::remove_reference<decltype(Iter(std::declval<T>()))>::type;

template <typename T>
using DeclareIterValueType = typename DeclareIterType<T>::ItemType;

namespace detail {

#ifndef __cpp_fold_expressions
namespace fold_expr {

inline bool AllOf(std::initializer_list<bool> list) {
  return std::find(list.begin(), list.end(), false) == list.end();
}

inline bool AnyOf(std::initializer_list<bool> list) {
  return std::find(list.begin(), list.end(), true) != list.end();
}

inline void ForEach(std::initializer_list<bool>) {}

}  // namespace fold_expr
#endif

template <typename T>
struct AnyValue {
  T value;
  AnyValue(T&& val) : value(std::forward<T>(val)) {}
  friend bool operator==(const AnyValue& a, const AnyValue& b) {
    return a.value == b.value;
  }
  friend bool operator!=(const AnyValue& a, const AnyValue& b) {
    return !(a.value == b.value);
  }
};

template <typename>
struct AlwaysFalse {
  enum { value = false };
};

template <typename... Types>
struct TypeSequence {};

template <typename First, typename Second>
class CompressedPair {
 public:
  CompressedPair(First first, Second second) : data_(first, second) {}
  First& first() { return std::get<0>(data_); }
  Second& second() { return std::get<1>(data_); }

 private:
  std::tuple<First, Second> data_;
};

struct NoneType {};

template <typename NewItemType, typename OldItemType, typename Extra = NoneType>
class IterableBase : public itertool::Iterable<NewItemType> {
 public:
  using ItemType = NewItemType;

  bool HasNext() override { return BaseGetIterator().HasNext(); }
  void Advance() override { return BaseGetIterator().Advance(); }
  bool IsFinite() override { return BaseGetIterator().IsFinite(); }
  size_t LengthHint() override { return BaseGetIterator().LengthHint(); }
  bool IsResetable() override { return BaseGetIterator().IsResetable(); }
  void Reset() override { BaseGetIterator().Reset(); }

 protected:
  using IteratorType = itertool::Iterator<OldItemType>;

  explicit IterableBase(IteratorType it, Extra extra = {}) : data_(it, extra) {}

  IteratorType& BaseGetIterator() { return data_.first(); }
  Extra& BaseGetExtra() { return data_.second(); }

 private:
  detail::CompressedPair<IteratorType, Extra> data_;
};

template <typename... T>
using IteratorTuple = std::tuple<Iterator<T>...>;

template <typename T>
using IteratorVector = std::vector<Iterator<T>>;

}  // namespace detail
}  // namespace itertool
